/*
**********************************************************
*
* Programme :	libliste.c
*
* ecrit par :	Najim Boujedli et Jeremy Paneri
*
* resume :		création et manipulation de liste doublement chaînée
* 
*
*
* date : 		01/02/13
*
***********************************************************
*/

#include <stdio.h>
#include <stdlib.h>

#include "libliste.h"

#include "typ.h"


/*
 * Fonction :		creerListe
 *
 * Parametres :		rien
 *
 * Retour :			TypVoisins*, liste initialisée à 1 élément
 *
 * Description :	créée une liste doublement chaînée initialisée avec la sentinelle
 *
 */

TypVoisins* creerListe(){
  
	TypVoisins* liste = (TypVoisins*) malloc(sizeof(TypVoisins));
	liste->voisin = -1;
	liste->poidsVoisin = 0;

	liste->voisinSuivant = liste;
	liste->voisinPrecedent = liste;
	

	
	return liste;

}


/*
 * Fonction :		ajouterVoisin
 *
 * Parametres :		TypVoisins* liste 	la liste à compléter
 *					int voisins 		le numéro du sommet à ajouter à la liste
 *					int poidsVoisin		le poids du sommet à ajouter à la liste
 *	
 * Retour :			0 	si l'ajout s'est effectué correctement, 
 *					-1  si le sommet existe déjà
 *
 * Description :	ajoute un sommet à liste de voisins
 *
 */

int ajouterVoisin(TypVoisins* liste, int voisin, double poids){
	
	// on vérifie que le voisin que l'on cherche à ajouter n'existe pas déjà
	int existe = rechercheVoisin(liste,voisin);
	if( existe == 1){
		return -1;
	}

	// s'il n'existe pas, on peut l'ajouter

	TypVoisins* prec = liste->voisinPrecedent;

	TypVoisins* newVoisin = (TypVoisins*) malloc(sizeof(TypVoisins));

	prec->voisinSuivant = newVoisin;

	newVoisin->voisin = voisin;
	newVoisin->poidsVoisin = poids;

	newVoisin->voisinPrecedent = prec;
	newVoisin->voisinSuivant = liste;

	liste->voisinPrecedent = newVoisin;

	return 0;
}

int supprimerVoisin(TypVoisins* liste, int voisin){
	
	TypVoisins* actu = liste;
	int existe = 0;

	if (actu==NULL) {
		// On évite d'accéder à une liste vide
		return -2;
	}

	do {
		if (actu->voisin == voisin){
			existe=1;
		}
		actu = actu->voisinSuivant;
	} while (!existe && actu->voisin != -1);

	if (existe == 0){
		// le sommet à supprimer n'existe pas
		return -1;
	}


	TypVoisins* aSuppr = actu->voisinPrecedent;

	TypVoisins* precASuppr = aSuppr->voisinPrecedent;
	TypVoisins* suivASuppr = aSuppr->voisinSuivant;

	precASuppr->voisinSuivant = aSuppr->voisinSuivant;
	suivASuppr->voisinPrecedent = aSuppr->voisinPrecedent;

	aSuppr->voisinSuivant = NULL;
	aSuppr->voisinPrecedent = NULL;

	free(aSuppr);

	return 0;
}


/*
 * Fonction :		rechercheVoisin
 *
 * Parametres :		TypVoisins* liste, la liste de recherche
 *					int voisin, le numéro du sommet à rechercher dans la liste
 *	
 * Retour :			0 	si le sommet n'existe pas
 *					1 	si le somme existe
 *
 * Description :	recherche la présence d'un sommet dans la liste de voisins
 *
 */

int rechercheVoisin(TypVoisins* liste, int voisin){

	TypVoisins* actu = liste;
	int existe = 0;

	do {
		// fprintf(stdout,"(%d/%d)\t",actu->voisin,actu->poidsVoisin);
		if (actu->voisin == voisin){
			existe=1;
		}
		actu = actu->voisinSuivant;
	} while (!existe && actu->voisin != -1);
	
	return existe;
}

/*
 * Fonction :		rechercheVoisinAvecPoids
 *
 * Parametres :		TypVoisins* liste, la liste de recherche
 *					int voisin, le numéro du sommet à rechercher dans la liste
 *					int poidsVoisin, le poids du sommet à rechercher dans la liste
 *	
 * Retour :			0 	si le sommet n'existe pas
 *					1 	si le somme existe
 *
 * Description :	recherche la présence d'un sommet 
 *					avec le poids correspondant dans la liste de voisins
 *
 */

int rechercheVoisinAvecPoids(TypVoisins* liste, int voisin, double poids){

	TypVoisins* actu = liste;
	int existe = 0;

	do {
		// fprintf(stdout,"(%d/%d)\t",actu->voisin,actu->poidsVoisin);
		if (actu->voisin == voisin && actu->poidsVoisin == poids){
			existe=1;
		}
		actu = actu->voisinSuivant;
	} while (!existe && actu->voisin != -1);
	
	return existe;
}

/*
 * Fonction :		sortieListe
 *
 * Parametres :		TypVoisins* liste, la liste à traiter
 *					FILE* output, le flux de sortie (ex: stdout)
 *
 * Retour :	 		rien
 *
 * Description :	fait ressortir la liste des voisins dans le flux indiqué
 *
 */

void sortieListe(FILE* output, TypVoisins* liste){

	TypVoisins* actu = liste;

	/*	
		Cette boucle permet d'afficher la liste des voisins 
		à condition de commencer par la sentinelle 
	*/
	while (actu->voisinSuivant->voisin != -1) {
		fprintf(output,"(%d/%f), ",actu->voisin,actu->poidsVoisin);
		actu = actu->voisinSuivant;
	}
	fprintf(output,"(%d/%f)\n",actu->voisin,actu->poidsVoisin);
}

/*
// Cette fonction ne permet pas d'eviter l'impression de la virgule

// void afficherListe(TypVoisins* liste){

// 	TypVoisins* actu = liste;
	
// 	do {
// 		fprintf(stdout,"(%d/%d)\t",actu->voisin,actu->poidsVoisin);
// 		actu = actu->voisinSuivant;
// 	} while (actu->voisin != -1);
		
// 	fprintf(stdout,"\n");
// }
*/




double getPoidsSommet(TypVoisins* liste, int voisin){

	TypVoisins* actu = liste;
	// int existe = 0;

	do {
		// fprintf(stdout,"(%d/%d)\t",actu->voisin,actu->poidsVoisin);
		if (actu->voisin == voisin){
			return actu->poidsVoisin;
		}
		actu = actu->voisinSuivant;
	} while (actu->voisin != -1);
	
	return 0;
}

/*
 * Fonction :		rechercheVoisinAvecPoids
 *
 * Parametres :		TypVoisins* liste, la liste de recherche
 *					int voisin, le numéro du sommet à rechercher dans la liste
 *					int poidsVoisin, le poids du sommet à rechercher dans la liste
 *	
 * Retour :			0 	si le sommet n'existe pas
 *					1 	si le somme existe
 *
 * Description :	recherche la présence d'un sommet 
 *					avec le poids correspondant dans la liste de voisins
 *
 */